package gold.enterprise;

import gold.utils.InputUtil;

import java.util.Arrays;

public class MicroSoft {

    public void heapSort(int[] nums) {
        int len = nums.length;
        for (int i = len / 2; i >= 0; i--) {
            adjustHeap(nums, i, len); //初始化堆
        }

//        for (int i = len - 1; i >= 0; i--) {
//            swap(nums, 0, i); //交换开始和最后位置的数字
//            adjustHeap(nums, 0, i);
//        }
    }


    public void adjustHeap(int[] nums, int start, int end) {
//        for (int i = start; i < end; ++i) {
//
//        }
        int maxIdx = start;
        if ((2 * start + 1) < end && nums[2 * start + 1] > nums[maxIdx]) maxIdx = 2 * start + 1;
        if ((2 * start + 2) < end && nums[2 * start + 2] > nums[maxIdx]) maxIdx = 2 * start + 2;

        if (maxIdx != start) {
            swap(nums, start, maxIdx);  //交互堆顶为左右子树最大节点
            adjustHeap(nums, maxIdx, end);
//            break;
        }

//        else {
//            break;
//        }

    }


//     sn = log(n) +  2*(log(n)-1 )+4*(log(n)-2 )+..    2/n * 1
//    2* sn = 2*logn + 4*(logn-1)+
//
//    = 1/8 *(n*(n+1))*log(n)  - sum(2^i * i)(i from 1 to n/2)
//
//    sn=2+4+8+16++n -long
//    sn=2n-2 -log(n)



    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        MicroSoft solution = new MicroSoft();
        int[] nums = InputUtil.toIntegerArray("[5,7,3,2,1]");
        solution.heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }


}
